package com.lfg.leetcode.leetcode100;

public class No123maxProfit {

    public static void main(String[] args) {
        int[] data = new int[]{1, 2, 4, 2, 5, 7, 2, 4, 9, 0};
        int ret = maxProfit(data);
        System.out.println("[" + ret + "]");
    }


    public static int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        return maxProfit(prices, 3);
    }

    public static int maxProfit(int[] prices, int k) {
        int[][] local = new int[prices.length][k + 1];
        int[][] global = new int[prices.length][k + 1];

        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                local[i][j] = Math.max(local[i - 1][j] + diff, global[i - 1][j - 1] + Math.max(diff, 0));
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);
            }
        }
        return global[prices.length - 1][k];
    }
}
